As network technology and sensor technology develop and proliferate, event stream processing aimed at real-time processing of sequences of events that occur in high volume every moment has received attention. A sequence of events is referred to as an event stream hereinafter. In the field of event stream processing, importance is placed on event-pattern matching technology of detecting a pattern of arrival order of events, and various methods have been proposed.
It is desired that event pattern matching has, for instance, three features described below. A first one of the features is described. It is preferable for the event pattern matching to ignore a noise event mixed in an event stream while performing matching. Meanwhile, a noise event denotes an event other than target events to be subjected to matching.
A second one of the features is described. It is preferable for the event pattern matching to perform efficient matching of various pattern expressions, such as a conjunction pattern and a disjunction pattern. For instance, a conjunction pattern of an event A and an event B is denoted as “A&B.” If both the events A and B are contained in an event stream in no particular order, “A&B” has been matched. A disjunction pattern of an event A and an event B is denoted as “AνB.” If any one of the events A and B is contained in an event stream, “AνB” has been matched.
A third one of the features is described. It is preferable for the event pattern matching to detect not only matching completion time of event pattern matching on an event stream in real time but also matching start time of event pattern matching on the event stream in real time.
Next, an example of a conventional technique for event pattern matching is described. FIG. 26 is a diagram for explaining the conventional technique according to A. Demers, et al., “Cayuga: A General Purpose Event Monitoring System,” Proc. CIDR, 2007. As illustrated in FIG. 26, an event stream 10 contains events “a”, “b”, “c”, “d”, “e”, “x”, “y”, and “z”. FIG. 27 is a diagram where events and descriptions about the events are associated with each other. As illustrated in FIG. 27, the event a represents issuance of a slip by a person in charge; the event b represents approval by a responsible department chief B; the event c represents approval by a responsible department chief C; the event d represents approval by a department chief D. The event e represents approval by a director E; the event x represents approval by a section chief X; the event y represents a login request from a user; the event z represents other process.
Assumed herein is a system that detects in real time only a slip that is processed through a proper process procedure and solicits settlement from a president. The proper process procedure is assumed as an event pattern P=(a, ((b&c)νd), e). This event pattern P denotes that patterns 1, 2, and 3 below are executed in order. The patterns 1, 2, and 3 may contain a noise event(s) therebetween.
The pattern 1 is issuance of a slip by a person in charge. The pattern 1 corresponds to “a” in the event pattern P.
The pattern 2 is execution of any one of sub-patterns 1 and 2 below. The sub-pattern 1 is approval by both the responsible department chief B and the responsible department chief C in no particular order. The sub-pattern 2 is approval by the department chief D. The pattern 2 corresponds to “(b&c)νd)” in the event pattern P.
The pattern 3 is approval by the director E. The pattern 3 corresponds to “e” in the event pattern P.
With a conventional technique according to J. Agrawal, et al., “Efficient Pattern Matching over Event Streams,” Proc. SIGMOD, 2008, the event pattern P is compared with the event stream 10 illustrated in FIG. 26. As a result, matching of the event a is performed at a position 10a in the event stream 10, and matching of the event c is performed at a position 10b. Furthermore, matching of the event b is performed at a position 10c, and matching of the event e is performed at a position 10d; hence, matching of the event pattern P is completed. According to the conventional technique, a settlement request notification is transmitted to the president when the matching is completed.
Meanwhile, in the conventional technique, comparison between an event pattern and an event stream is performed by building and utilizing a nondeterministic finite automaton (NFA) that corresponds to the event pattern. A nondeterministic finite automaton is abbreviated as an automaton hereinafter. FIG. 28 is a diagram illustrating a conventional automaton built from an event pattern. An automaton 20 illustrated in FIG. 28 is an automaton corresponding to the event pattern P=(a, ((b&c)νd), e).
The automaton 20 joins nodes 21, 22, 23a to 23f, 24a to 24f, 25a to 25f, 26a to 26f, 27, and 28. With the conventional technique, all the combinations of occurrence order of “b,” “c,” and “d” are expressed with the nodes 23a to 23f, 24a to 24f, 25a to 25f, and 26a to 26f to adapt to the conjunction pattern “b&c&d” of the event pattern P. Occurrence of an event over an arrow invokes a node transition of the automaton 20. For instance, a transition from the node 21 to the node 22 is invoked by arrival at the position of the event a in the event stream.
Meanwhile, “ε” of the automaton 20 represents an ε-transition. For instance, when a transition from the node 21 to the node 22 is invoked, ε-transitions from the node 22 to the nodes 23a to 23f are invoked.
For instance, when an event stream is assumed as “a, b, c, d, and e,” matching is completed by transitions in the order of the nodes 21, 22, 23a, 24a, 25a, 26a, 27, and 28 of the automaton 20.
However, the conventional technique described above is disadvantageous in being incapable of efficient event pattern matching by utilizing an automaton.
When an event pattern contains a conjunction pattern, as illustrated in FIG. 28, an automaton is to include all the combinations of occurrence order of events contained in the conjunction pattern, which is inefficient. For instance, when a conjunction pattern contains m events, the number of nodes is O(m!).